|
In cryptography, coincidence counting is the technique (invented by William F. Friedman〔 The original application ignored normalization.〕) of putting two texts side-by-side and counting the number of times that identical letters appear in the same position in both texts. This count, either as a ratio of the total or normalized by dividing by the expected count for a random source model, is known as the index of coincidence, or IC for short. ==Calculation== The index of coincidence provides a measure of how likely it is to draw two matching letters by randomly selecting two letters from a given text. The chance of drawing a given letter in the text is (number of times that letter appears / length of the text). The chance of drawing that same letter again (without replacement) is (appearances - 1 / text length - 1). The product of these two values gives you the chance of drawing that letter twice in a row. One can find this product for each letter that appears in the text, then sum these products to get a chance of drawing two of a kind. This probability can then be normalized by multiplying it by some coefficient, typically 26 in English. : :Where ''c'' is the normalizing coefficient (26 for English), ''n''a is the number of times the letter "a" appears in the text, and ''N'' is the length of the text. We can express the index of coincidence IC for a given letter-frequency distribution as a summation: : where ''N'' is the length of the text and ''n''1 through ''nc'' are the frequencies (as integers) of the ''c'' letters of the alphabet (''c'' = 26 for monocase English). The sum of the ''ni'' is necessarily ''N''. The products count the number of combinations of ''n'' elements taken two at a time. (Actually this counts each pair twice; the extra factors of 2 occur in both numerator and denominator of the formula and thus cancel out.) Each of the ''ni'' occurrences of the ''i''-th letter matches each of the remaining occurrences of the same letter. There are a total of letter pairs in the entire text, and 1/''c'' is the probability of a match for each pair, assuming a uniform random distribution of the characters (the "null model"; see below). Thus, this formula gives the ratio of the total number of coincidences observed to the total number of coincidences that one would expect from the null model.〔 Published in two parts.〕 The expected average value for the IC can be computed from the relative letter frequencies of the source language: : If all letters of an alphabet were equally distributed, the expected index would be 1.0. The actual monographic IC for telegraphic English text is around 1.73, reflecting the unevenness of natural-language letter distributions. Sometimes values are reported without the normalizing denominator, for example for English; such values may be called ''κ''p ("kappa-plaintext") rather than IC, with ''κ''r ("kappa-random") used to denote the denominator (which is the expected coincidence rate for a uniform distribution of the same alphabet, for English). 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Index of coincidence」の詳細全文を読む スポンサード リンク
|